---
title: "4、方格分割"
created: 2025-11-28
tags:
  - 算法
---

# 4、方格分割

## 题目 [方格分割](https://www.lanqiao.cn/paper/3854/problem/644/)

![[image-b1e91fbf.png]]

## 思路分析

两部分是围绕中心点对称的

想法是 用1表示一种颜色 0表示另一种颜色 枚举所有的排列情况

然后找到所有应该对称的下标组 对他们进行判断 如果发现某位置的对应位置不是相反 就直接continue

如果所有对称位置都符合01相反 就说明是一个可行方案

![[image-c5fc6cc1.png]]

a[i][j]应该要与a[7-i][7-j]对称

但是不好对每个方格放01进行枚举

想了一下 可以转换成一维 用二进制数来枚举

![[image-3bbe6bd8.png]]

![[image-53326c15.png]]

因为二进制数每一位都是0或1 那么从0枚举到2^36 就可以考虑到所有的排列组合

看某个方案是否满足 只需要看某一位 和它对应的那一位为是否不一样即可

对应关系如下：

![[image-c5cb49e8.png]]

然后实际上二进制是从第0位开始的 所以关系应该是 i：36-i

所以得到以下代码

```cpp
#include<bits/stdc++.h>

using namespace std;

int main()

{

  long long cnt=0;

  for(long long i=0;i<(1LL<<36);i++){

    bool success=true;

    for(int d=0;d<18;d++){

      long long curd = (i >> d) & 1LL;

      long long backd = (i >> (35 - d)) & 1LL;

      if(curd==backd){

        success=false;

        break;

      }

    }

    if(success) cnt++;

  }

  cout<<cnt/4;

  return 0;

}
```

看似很巧妙 实际……

由于$2^{36}$ 的数量级极其庞大（超过687亿），即便每秒处理数百万个模式的速度运行,完成整个枚举也将花费几个小时到几天不等……

（把笔记本放那里跑了 看看3.5小时能不能出结果hh）

这题正解是用dfs

因为涉及到了方格图和方法数

因为中心对称 所以只需要考虑一边的所有组合 用dfs可以考虑到所有的情况 在往某方向走的时候 它的对应的点也要相应被标记 如果发现对应的点已经被标记过了
就说明这条路径不成立 直接回溯考虑其他路径

其实和刚才的枚举思路应该是差不多的 都是枚举一半的所有组合情况 看对面状态 一旦发现不一样就找下一个 但是因为dfs的减枝是比较强大的 即发现某个点不可行了
所有要经过该点的路径就都被剪去了 显然二进制枚举的方式无法做到这点 即使一发现某位不一样就break 也会浪费很多时间

DFS的剪枝效果

**即时剪枝**：在DFS中，一旦确定某条路径不可能满足条件（如违反了对称性），就会立即停止进一步探索这条路径，回溯到上一个决策点尝试其他选项。这种即时剪枝意味着大量潜在的无效路径根本不会被探索。

**避免重复工作**：通过在探索过程中记录哪些路径已经被证明是无效的，DFS避免了重复检查这些路径，进一步提高了效率。

二进制枚举的局限

**盲目枚举**：尽管二进制枚举试图通过只检查一半的位来减少工作量，但它本质上仍然是一种盲目的方法，因为它必须生成并检查每个可能的组合。在发现某个组合不满足条件后，它不能利用这个信息来避免生成其他类似的、同样无效的组合。

**无法有效剪枝**：即使在检测到对称位不匹配时立即停止，每次循环仍然从头开始，为每个可能的组合分配时间，这导致了大量的无效计算。

思路：

从网格的中心点开始。

向四个方向探索，每次探索时同时标记当前点和对称点。

如果探索到边界，则认为找到了一种有效的分割方式。

由于是沿着边界分割，所以实际上探索的是网格中的点，而不是单元格。

看来有必要补一下dfs的部分了

![[image-776717fc.png]]

问题变成了 从中心点开始 找到一条走到边界 的路径 另一半是完全对称的

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;
#define endl '\n'

const int N=7;//0~6

bool st[N][N];

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

int res=0;

int n;

bool isVaild(int x,int y){

	return x>=0 && x<=N-1 && y>=0 && y<=N-1 && !st[x][y];

}

void dfs(int x,int y){

	if(x==0 || x==n || y==0 || y==n){

		res++;

		return;

	}

	for(int i=0;i<4;i++){

		int nx=x+dx[i],ny=y+dy[i];

		if(isVaild(nx,ny) && isVaild(n-nx,n-ny)){

			st[nx][ny]=st[n-nx][n-ny]=true;

			dfs(nx,ny);

			st[nx][ny]=st[n-nx][n-ny]=false;//该点可以走多次 需要回溯

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	n=N-1;

	st[n/2][n/2]=true;

	dfs(n/2,n/2);

	cout<<res/4<<endl;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[3、承压计算|3、承压计算]] 🏠 [[00-刷题理模型]] ➡️ [[5、日期问题|5、日期问题]]